#include <iostream>
#include <vector>
#include <string>
 
using namespace std;

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        string tmp="";
        dfs(s,tmp,0,0,res);
        return res;

    }

private:
    // str:要分解为ip的字符串，tmp,还未分解完成的字符串，cur：当前指向str的cur位置，num:分解的段数，res:满足条件则放入结果res中
    void dfs(string& str,string& tmp,int cur,int num,vector<string>& res){
        if(num==4&&cur==str.size()){
            //分解为4分，而且当前超出str的范围
            res.push_back(tmp);
            return;
        }else if(num<4&&cur<str.size()){
            //除第一段外，都要加上'.'
            if(cur>0){
                tmp.push_back('.');
            }
        }else{
            //其余的不符合条件，返回
            return;
        }
        
        
        string part="";//每次去除的字符串，长度可为1,2,3
        int int_str=0;
        for(int i=1;i<=3;i++){
            part=str.substr(cur,i);
            int_str=stoi(part);//转化为数字
            string last="";//记录转换前的字符串
            //i==1时不管什么情况都可以进行分解，i>1时，int_str>pow(10,i-1)而且<=255
            if((i==1)||(i>1&&int_str>=pow(10,i-1)&&int_str<=255)){
                last=tmp;//添加前tmp
                tmp=tmp+part;//假设加上去分割的这一段
                //cout<<"tmp:"<<tmp<<" part:"<<part<<endl;
                dfs(str,tmp,cur+i,num+1,res);
                tmp=last;//修改回去
                //cout<<"after erase tmp:"<<tmp<<endl;
            }
        }
    }
};

int main(){

    string code="25525511135";
    Solution s;
    vector<string> res;
    res=s.restoreIpAddresses(code);
    return 0;
}